import java.util.*;

public class Test2 {

    public static void main(String[] args) {
//        String[] words = {"aa","aa"};
//        List<Integer> list = findSubstring("aaaaaaaaaaaaaa",words);
//        System.out.println(list);

        String str = minWindow("bba","ba");
        System.out.println(str);

    }

    public String minWindow1(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int[] hash1 = new int[128];//用数组模拟哈希表
        int kinds = 0;//标记t中有多少种字符
        for (char ch:t){
            if (hash1[ch]==0){
                kinds++;
            }
            hash1[ch]++;
        }
        int[] hash2 = new int[128];


        int minlen = Integer.MAX_VALUE;
        int begin = -1;

        for (int left = 0,right = 0,count = 0;right<s.length;right++){
            char in = s[right];
            hash2[in]++;
            if (hash2[in]==hash1[in]) count++;

            while (kinds==count){
                if (right-left+1<minlen){
                    begin=left;
                    minlen = right-left+1;
                }
                char out = s[left];
                left++;
                if (hash2[out]==hash1[out]){
                    count--;
                }
                hash2[out]--;

            }

        }
        if (begin == -1){
            return new String();
        }else {
            return ss.substring(begin,begin+minlen);
        }



    }




    //最小覆盖子串
    public static String minWindow(String s, String t) {
        int left = 0;
        int right = 0;
        int count = 0;//表示当前有效字符
        HashMap<Character,Integer> hash1 = new HashMap<>();
        HashMap<Character,Integer> hash2 = new HashMap<>();
        int len = Integer.MAX_VALUE;//当前最小的窗口
        int tmpl = -1;//暂存最小窗口的left下标
        int tmpr = -1;//暂存最小窗口的right下标

        //将t存放到hash2
        for (int i = 0;i<t.length();i++){
            hash2.put(t.charAt(i),hash2.getOrDefault(t.charAt(i),0).intValue()+1);
        }


        while (right<s.length()){

            char charR = s.charAt(right);
            hash1.put(charR,hash1.getOrDefault(charR,0).intValue()+1);//将right指向的字符存到hash1
            if (hash1.get(charR).intValue() == hash2.getOrDefault(charR,0).intValue()){
                //此时是有效字符
                count++;
            }
            right++;

            //窗口成立时
            while (count == hash2.size()){
                //先更新一下窗口
               if(right-left+1 < len){
                   tmpl = left;
                   len = right-left+1;
               }

                //移动left指针，不成立

                if (hash1.get(s.charAt(left)).intValue() == hash2.getOrDefault(s.charAt(left),0).intValue()){
                    count--;
                }
                hash1.put(s.charAt(left),hash1.get(s.charAt(left)).intValue()-1);
                left++;
            }

        }
        //最后返回 tmpl 和 tmpr之间的数
//        char[] str1 = new char[len];
        if (tmpl == -1){
            return new String();
        }else {
            return s.substring(tmpl,tmpl+len);
        }


    }



    //串联所有单词的子串
    public static List<Integer> findSubstring(String s, String[] words) {
        Map<String,Integer> hash1 = new HashMap<>();
        for (String str:words) hash1.put(str,hash1.getOrDefault(str,0)+1);
        List<Integer> list = new ArrayList<>();
        int len = words[0].length();
        int m = words.length;
        for (int i=0;i<len;i++){
            Map<String,Integer> hash2 = new HashMap<>();//保存窗口内单词
            for (int left =i,right=i,count=0;right+len<=s.length();right+=len){
                //进窗口
                String in = s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if (hash2.get(in)<=hash1.getOrDefault(in,0)) count++;
                //判断
                if (right-left+1 > len*m){
                    //出窗口+维护窗口
                    String out = s.substring(left,left+len);
                    if (hash2.get(out)<=hash1.getOrDefault(out,0)) count--;
                    hash2.put(out, hash2.get(out)-1);
                    left+=len;
                }
                //更新结果
                if (count==m){
                    list.add(left);
                }

            }
        }
        return list;

    }



    //串联所有单词的子串
    public static List<Integer> findSubstring1(String s, String[] words) {
        int left=-1,right=-1;
        int count = 0;//记录有效字符串
        List<Integer> list = new ArrayList<>();
        //hash表
        HashMap<String,Integer> hash1 = new HashMap<>();
        HashMap<String,Integer> hash2 = new HashMap<>();

        //每个字符串的长度
        int len = words[0].length();

        //现将words存入hash2中
        for (String a:words){
            if (hash2.containsKey(a)){
                int old = hash2.get(a);
                hash2.put(a,old+1);
            }else {
                hash2.put(a,1);
            }
        }

        //滑动窗口一共滑动多少次
        for(int i=-1;i<len-1;i++){
            //每滑动一次，left 和 right都有重置
            left = i;
            right=i;
            count = 0;
            hash1 = new HashMap<>();
            //开始一次的滑动窗口
            while (right-left < len * words.length){
                //right一次走len格
                char[] tmp1 = new char[len]; // 暂时存储right扫过的字符
                for(int j = 0;j<len;j++){
                    right++;
                    tmp1[j] = s.charAt(right);
                }
                //right没扫过一个字符串，判断是否是有效字符
                String str1 = String.valueOf(tmp1);
                if (hash1.containsKey(str1)){ //如果存在str1
                    int old = hash1.get(str1);
                    hash1.put(str1,old+1);
                }else {
                    hash1.put(str1,1); //不存在则加入
                }
                if (hash2.containsKey(str1) && hash1.get(str1)<=hash2.get(str1)){
                    //如果hash2中有此key，并且hash1中的value 小于 等于hash2中的value
                    count++;
                }
            }
            //判断是否符合条件
            if (count == words.length){
                list.add(left+1);
            }

            //窗口已经到达固定长度
            while (right+len < s.length()){
                //到固定长度后，right和left同时向右移动

                //right一次走len格
                char[] tmp1 = new char[len]; // 暂时存储right扫过的字符
                for(int j = 0;j<len;j++){
                    right++;
                    tmp1[j] = s.charAt(right);
                }
                //right没扫过一个字符串，判断是否是有效字符
                String str1 = String.valueOf(tmp1);
                if (hash1.containsKey(str1)){ //如果存在str1
                    int old = hash1.get(str1);
                    hash1.put(str1,old+1);
                }else {
                    hash1.put(str1,1); //不存在则加入
                }
                if (hash2.containsKey(str1) && hash1.get(str1)<=hash2.get(str1)){
                    //如果hash2中有此key，并且hash1中的value 小于 等于hash2中的value
                    count++;
                }

                //left一次走len格
                char[] tmp2 = new char[len]; // 暂时存储right扫过的字符
                for(int j = 0;j<len;j++){
                    left++;
                    tmp2[j] = s.charAt(left);
                }
                //right没扫过一个字符串，判断是否是有效字符
                String str2 = String.valueOf(tmp2);
                if (hash2.containsKey(str2) && hash1.get(str2) <= hash2.get(str2)){
                    //如果hash2中有此key，并且hash1中的value 小于 等于hash2中的value
                    count--;
                }
                if (hash1.containsKey(str2)){ //如果存在str2
                    int old = hash1.get(str2);
                    hash1.put(str2,old-1);
                }
                if(hash1.containsKey(str2) && hash1.get(str2) == 0){
                    hash1.remove(str2);
                }
                //判断是否符合条件
                if (count == words.length){
                    list.add(left+1);
                }
            }
        }

        return list;
    }


    public static List<Integer> findAnagrams(String s, String p) {

        int left = 0;
        int right = 0;
        int count = 0;//记录有效字符，判断两个hash表是否相等时使用
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        List<Integer> list = new ArrayList<>();

        //先将p字符串放到hash2中
        for(int i = 0;i<p.length();i++){
            hash2[p.charAt(i)]++;
        }

        while (right-left+1 <= p.length()){
            hash1[s.charAt(right)]++;
            if (hash1[s.charAt(right)] <= hash2[s.charAt(right)]){
                count++;
            }
            right++;
        }

        //判断有效字符的个数
        if (count==p.length()){
            list.add(left);
        }

        while (right<s.length()){
            //加入right指向的字符
            hash1[s.charAt(right)]++;
            if (hash1[s.charAt(right)] <= hash2[s.charAt(right)]){
                count++;
            }
            right++;



            //判断left指向的字符是否有效

            if (hash1[s.charAt(left)] <= hash2[s.charAt(left)]){
                //有效字符
                count--;
            }
            hash1[s.charAt(left)]--;
            left++;



            //判断有效字符的个数
            if (count==p.length()){
                list.add(left);
            }


        }
        return list;


    }



    public int totalFruit(int[] f) {
        int left = 0;
        int right = 0;
        int n = f.length;
//        HashMap<Integer,Integer> hash = new HashMap<>();
        int len = 0;
        int[] hash = new int[n+1];
        int kinds = 0;

        for (left = 0,right=0,kinds = 0;right<n;right++){
            int in = f[right];
            if (hash[in] == 0)
                kinds++; // 维护水果的种类
            hash[in]++;//进窗口

            while (kinds>2){ //篮子里有几种水果
                int out = f[left++];
                hash[out]--;//出窗口
                if (hash[out] == 0){
                    kinds--;
                }
            }
            //更新结果
            len = Math.max(len,right-left+1);
        }
        return len;

    }



    // leetcode 水果成篮
    public int totalFruit1(int[] fruits) {
        int left = 0;
        int right = 0;
        int n = fruits.length;
        int[] hash = new int[n+1];
        int len = 0;
        int kinds = 0;//用来记录当前篮子里水果的种类

        while (right<n){
            //如果哈希表中存在当前元素
            if (hash[fruits[right]] != 0){
                hash[fruits[right]]++;
            }else {
                //如果不存在则判断是否已满
                if (kinds==2){
                    //在left移动之前判断当前子数组的长度
                    len = Math.max(len,right-left);
                    //移动left
                    while (kinds!=1){
                        hash[fruits[left++]]--;
                        if (hash[fruits[left-1]]==0){
                            kinds--;
                        }
                    }
                    right--;
                }else {
                    //篮子不满，放入当前水果
                    hash[fruits[right]]++;
                    kinds++;
                }
            }
            right++;
        }
        len = Math.max(len,right-left);
        if(len == 0){
            return n;
        }

        return len;

    }



    public int minOperations(int[] nums, int x) {


        int n = nums.length;
        int left = 0,right = 0;
        int sum = 0;
        for(int a:nums){
            sum +=a;
        }
        int target = sum-x;
        if (target<0){ //细节
            return -1;
        }
        int tmp = 0;
        int len = -1;

        while (right<n){
            tmp+=nums[right];
            right++;
            while (tmp>target){
                tmp-=nums[left];
                left++;
            }
            if (tmp==target){
                len = Math.max(len,right-left);
            }
        }
        if (len == -1){
            return -1;
        }
        return nums.length-len;
    }

    public int longestOnes(int[] nums, int k) {

        int ret = 0;
        for(int left = 0,right = 0,zero = 0;right<nums.length;right++){
            if (nums[right]==0) zero++;
            while (zero>k){
                if (nums[left++]==0) zero--;
            }
            ret = Math.max(ret,right-left);
        }

        return ret;

    }



    //最大连续1的个数
    public int longestOnes1(int[] nums, int k) {
        int zero = 0;
        int left = 0;
        int right = 0;
        int len = 0;

        //当right<nums.length 时，进入循环
        while (right < nums.length){
            //right向右移动
            while (right < nums.length && zero <= k){
                if (nums[right] == 0){
                    zero++;
                }
                right++;
            }
            //zero等于k之后移动left,如果right没有走到头时，zero大于k，left向右移动
            if(zero>k){
                if (nums[left] == 0){
                    zero--;
                }
                left++;
            }
            if (len<(right-left)){
                len = right-left;
            }

        }
        return len;
    }

    //无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        //定义一个整型数组，代替hash表
        int[] num = new int[128];
        //定义左右指针，代表滑动窗口的边界
        int left = 0;
        int right = 0;
        int len = 0;

        while (right<s.length()){ // right到达字符串的最右边停止循环
            //判断当前哈希表中有没有right所指的字符
            if (right<s.length() && num[s.charAt(right)] == 0){ //没有，则将字符存入哈希表，数组改为1,接着移动right
                num[s.charAt(right)] = 1; // 将字符存入哈希表
                right++;
                //移动一次更新一次len
                if (len<(right-left)){
                    len = right-left;
                }
            }else {  //如果存在，移动left到合适的位置
                while (s.charAt(left)!=s.charAt(right)){  //将哈希表中重复字符的左边的字符弹出哈希表
                    num[s.charAt(left)] = 0;
                    left++;
                }
                num[s.charAt(left)] = 0;  //将哈希表中的重复字符弹出
                left++;
            }

        }
        return len;
    }


    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length,sum=0,len = Integer.MAX_VALUE;
        for(int left = 0,right = 0;right<n;right++){
            sum += nums[right];  //进窗口
            while (sum>=target){  //判断
                len = Math.min(len,right-left+1);
                sum-=nums[left++];  //出窗口
            }
        }
        if (len == Integer.MAX_VALUE){
            return 0;
        }
        return len;
    }











    public int minSubArrayLen1(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int len = nums.length;

        while (right<=nums.length){
            //循环结束时，要么sum>=target
            while (right<nums.length && sum<target){
                sum+=nums[right];
                right++;
            }
            if(sum<target && left != 0){
                return len;
            }else if(sum<target && left == 0){
                return 0;
            }
            //更新len
            if (len>(right-left)){
                len = right-left;
            }
            if (len==1){
                return 1;
            }
            sum-=nums[left];
            left++;
        }
        return len;
    }






}
